package com.mamingchao.basic.swardToOffer.three;

public class MarkLetters {
    
    /**
     * 计算可以标记字母的最大分数
     * @param s 输入字符串
     * @return 最大分数
     */
    public static int getMaxScore(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        
        int n = s.length();
        // dp[i] 表示前i个字符可以获得的最大分数
        int[] dp = new int[n + 1];
        
        // 初始化
        dp[0] = 0;
        dp[1] = 0;
        
        for (int i = 2; i <= n; i++) {
            // 不标记当前字符和前一个字符
            int option1 = dp[i - 1];
            
            // 尝试标记当前字符和前一个字符
            int option2 = 0;
            char prev = s.charAt(i - 2);
            char curr = s.charAt(i - 1);
            
            // 检查是否可以标记（相同或相邻）
            if (prev == curr || Math.abs(prev - curr) == 1) {
                int score = (prev - 'a' + 1) + (curr - 'a' + 1);
                option2 = dp[i - 2] + score;
            }
            
            // 取最大值
            dp[i] = Math.max(option1, option2);
        }
        
        return dp[n];
    }
    
    public static void main(String[] args) {
        // 测试用例1
        String s1 = "abdbb";
        System.out.println("测试用例1 - 输入: " + s1);
        System.out.println("预期结果: 7");
        System.out.println("实际结果: " + getMaxScore(s1));
        
        // 测试用例2
        String s2 = "abc";
        System.out.println("\n测试用例2 - 输入: " + s2);
        System.out.println("预期结果: 3");
        System.out.println("实际结果: " + getMaxScore(s2));
        
        // 测试用例3
        String s3 = "aabb";
        System.out.println("\n测试用例3 - 输入: " + s3);
        System.out.println("预期结果: 6");
        System.out.println("实际结果: " + getMaxScore(s3));
        
        // 测试用例4
        String s4 = "zyx";
        System.out.println("\n测试用例4 - 输入: " + s4);
        System.out.println("预期结果: 51");
        System.out.println("实际结果: " + getMaxScore(s4));
    }
} 